package 动态规划;


import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/5 12:20
 */
public class leetcode6310获得分数的方法数 {

    /*
     多重背包
     */
    public static final int MOD = 1000000007;

    public int solution(int target,int types[][]){
        int dp[][] = new int[types.length + 1][target + 1];
        for(int [] arr : dp){
            Arrays.fill(arr,-1);
        }
        return recursion(0,types,target,dp);
    }

    public int recursion(int index,int types[][],int rest,int dp[][]){
        if(rest == 0){
            return 1;
        }
        if(index == types.length || rest < 0){
            return 0;
        }
        if(dp[index][rest] != -1){
            return dp[index][rest];
        }
        int ans = 0;
        for(int count = 0;count <= types[index][0];count++){
            ans += recursion(index + 1,types,rest - count * types[index][1],dp);
            ans = ans % MOD;
        }
        return dp[index][rest] = ans % MOD;
    }

    /*
     dp 版本
     */
    public int dp(int target,int types[][]){
        int dp[][] = new int[types.length + 1][target + 1];
        dp[types.length][0] = 1;
        for(int index = types.length - 1;index >= 0;index--){
            dp[index][0] = 1;
            for(int rest = 1; rest <= target;rest++){
                int ans = 0;
                for(int count = 0;count <= types[index][0];count++){
                    if(rest - count * types[index][1] >= 0){
                        ans += dp[index + 1][rest - count * types[index][1]];
                    }
                    ans = ans % MOD;
                }
                dp[index][rest] = ans;
            }
        }
        return dp[0][target];
    }
    /*
     这个 题的 数据 规模比较的小， 上面的时间 复杂度 也可以过！
     其实， 还可以 进行斜率 优化的 操作的！
     留到后面有时间 再去思考吧！
     */

}
